package com.example.rwq_test.niuke.stack;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * 滑动窗口最大值
 *
 * @author renweiqiang
 * @version 1.0.0
 * @createTime 2023/12/6
 */
public class SlipWinMax {
    public static void main(String[] args) {
        int[] num = {9, 8, 7, 4 ,5, 6, 9, 8, 7};
        int[] res = maxInWindows(num, 3);
        System.out.println(Arrays.toString(res));
    }

    public static int[] maxInWindows(int[] num, int size) {
        if (num == null || num.length == 0 || size <= 0 || size > num.length) {
            return new int[0];
        }
        if (size == 1) {
            return num;
        }
        int[] res = new int[num.length - size + 1];
        int index = 0;
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < num.length; i ++) {
            while (!deque.isEmpty() && num[deque.peekFirst()] < num[i]) {
                deque.pollFirst();
            }
            deque.offerFirst(i);
            if (i >= size - 1) {
                res[index++] = num[deque.peekLast()];
            }
            if (deque.peekLast() == i - size +1) {
                deque.pollLast();
            }
        }
        return res;
    }
}
